package logic;

public class TwoOptBit {
	
	public static Tour twoOpt(Graph g, Tour tour) {
		for (int l = 0; l < 20; l++) {
			for (int i = 0; i < tour.size(); i++) {
				Vertex t1 = g.vertices[i];
				Vertex t2 = tour.next(t1);
				Vertex t4 = null;
				Vertex t3 = null;
				for (Vertex n : t1.topk) {
					t3 = n;
					t4 = tour.prev(t3);
					int u1 = g.distMatrix[t3.index][t4.index];
					int v1 = g.distMatrix[t1.index][t2.index];
					int u2 = g.distMatrix[t1.index][t4.index];
					int v2 = g.distMatrix[t3.index][t2.index];
					if (t2 != n && (u1 + v1 > u2 + v2)) {
						if (t2 == t4) {
							t3 = null;
							continue;
						}
						break;
					} else {
						t3 = null;
					}
				}
				if (t3 != null) {
					tour.flip(t1,t2,t3,t4);
				}
			}
		}
		return tour;
	}
}